class Trie {
private:
    vector<Trie*> child;
    bool isEnd;
    Trie* serachRight(string s){
        Trie* cur = this;
        for(char e : s){
            int c = e - 'a';
            if(cur->child[c] == NULL){
                return NULL;
            }
            cur = cur->child[c];
        }
        return cur;
    }
public:
    Trie():child(26)
        ,isEnd(false)
    {
        
    
    }
    
    void insert(string word) {
        Trie* cur = this;
        for(char e : word){
            int c = e - 'a';
            if(! cur->child[c]){
                cur->child[c] = new Trie();
            }
            cur = cur->child[c];
        }
        cur->isEnd = true;
    }
    
    bool search(string word) {
        Trie* node = serachRight(word);
        return node != NULL && node->isEnd == true;
    }
    
    bool startsWith(string prefix) {
        return serachRight(prefix) != NULL;
    }
};
